package src.dynamic_programming;

/**
 * @author starsea
 * @date 2024-08-26 10:17
 */

public class Test07 {
    public static void main(String[] args) {
        String s = "babad";
        String ans=longestPalindrome(s);
    }
    public static String longestPalindrome(String s) {
        s=" "+s;
        char[] arr=s.toCharArray();
        int n=arr.length;
        boolean[][] dp=new boolean[n][n];
        int a=0;
        int max=0;
        dp[0][0]=true;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(arr[i]==arr[j])
                {
                    dp[i][j]=i==j || i+1==j || dp[i-1][j-1];
                }else
                {
                    dp[i][j]=false;
                }
                if(dp[i][j]==true)
                {
                    if(j-i+1>=max)
                    {
                        max=j-i+1;
                        a=i;
                    }
                }
            }
        }
        String ans=s.substring(a,a+max);
        return ans;



    }
}
